Various methods of memory allocation and deallocation for computer systems are known.
FIG. 1 of the accompanying drawings schematically illustrates a computer system 100. The computer system 100 comprises a processor 102 and a memory, such as a random access memory (RAM) 104. The computer system 100 may be, for example, a personal computer, a portable device (such as a mobile telephone or a personal digital assistant), an embedded system, a network of several computers, or any computing platform, etc. It will be appreciated that the computer system 100 may comprise more than one processor 102, with these processors either operating independently of each other or working together. It will also be appreciated that the computer system 100 may comprise one or more RAMs 104. Processors 102 and RAMs 104 are well-known, as are methods of providing them in an apparatus (computer system 100), and shall therefore not be described in more detail herein.
The processor 102 executes one or more applications, processes, threads or tasks in order to carry out the functionality required of the computer system 100. Execution of an application may involve executing one or more associated processes, threads or tasks. Throughout this specification, the terms “application”, “process”, “thread” and “task” will be used as synonyms, and the skilled person will recognise that this specification applies equally to memory allocation and deallocation for applications, processes, threads or tasks.
To execute a process, the processor 102 will receive, store, modify, operate on and output various data. Some of this data may be used merely as intermediate data during processing of the process; other data may be input data received from a source (such as a human user) external to the process; other data may be output data that is an end-product of the process. The processor 102 stores data in the memory 104 and can access and modify the data stored in the memory 104. As such, one or more respective regions of the memory 104 are allocated (or assigned) to each of the processes being executing.
Allocation of memory for a process may be performed by so-called “static memory allocation”, or “dynamic memory allocation”, or both. These are described in more detail below.
Static memory allocation involves a fixed amount of memory being reserved for (or allocated to) a process at compile-time, i.e. when the program code (or software) for that process is initially written and then compiled to form executable software. For example, the memory for constant data, such as string literals, and global variables is usually statically allocated. At the beginning of execution of the process, a region of the memory 104 that is large enough for that process's static memory allocations is allocated to that process. This memory region is maintained throughout the run-time of the process for use by that process, and is only released (or freed) once that process has been terminated. Once this memory region has been freed, some or all of that memory region may be allocated to another process.
Additionally, at the beginning of execution of a process, another fixed size region of the memory 104, called the “stack”, may be allocated to that process. The stack is used for a variety of purposes, such as for storing local variables (i.e. variables used solely within a given block of program code) and for storing the instruction address to which processing should return on completion of an active subroutine of that process.
Dynamic memory allocation involves a process requesting, at run-time, the allocation of a contiguous region (i.e. a contiguous block or area or buffer) of currently unused (i.e. free, unallocated or available) memory from the memory 104. Dynamic memory allocation is usually performed from a section of the memory 104, called the “heap”, that is reserved just for dynamic memory allocation. Dynamic memory allocation is often performed, for example, when the size of memory required for a particular purpose is not known at compile-time, with this size only becoming known during run-time. For example, the amount of memory required to store an image will depend on the dimensions of that image, and these dimensions may only be known from the input from a user (i.e. during run-time rather than during compile-time). Whilst the programmer could elect to statically allocate enough memory (for example, based on a worst-case-estimate predicting the largest amount of memory that could possibly be required), this would be inefficient memory usage as it leaves less of the memory 104 available for use by other processes.
There are various methods well known in this field of technology by which the processor 102, and the operating system being used by the computer system 100, may manage the memory on the heap so that the processor 102 can distinguish between regions of the memory 104 that have been allocated and regions of the memory 104 that are free. This allows the processor 102 to find a free region of the memory 104 when a dynamic memory allocation request is received. For example, each contiguous region of allocated memory and each contiguous region of free memory may be provided with a header and a footer that store an indicator of whether that region is allocated or is free, together with an indication of the size of that region. Adjacent regions of free memory may be merged together to form a single larger region of free memory with a single header and footer. Thus, the processor 102 can traverse between regions of the memory using the size values indicated in the headers and footers. A dynamic memory allocation request for a specific amount of memory will involve finding a region of the memory 104 that is marked as being free and that is sufficiently large to provide at least the requested amount of memory for the requesting process (together with any headers and footers that need to be maintained). The headers and footers for the regions are then updated accordingly, so that the memory region that is now allocated for the requesting process is identified as having been allocated. It will be appreciated, though, that other mechanisms may be used to allow the processor 102 to distinguish between regions of the memory 104 that have been allocated and regions of the memory 104 that are free.
In the C programming language, a dynamic memory allocation request can be achieved by calling (or executing or performing or running) the C-library function void* malloc (size_t size). This function has an input parameter, size, representing the amount of memory that the process wishes to have allocated, and returns a pointer to (or identifier of) the allocated memory region. Execution of the malloc function at run-time causes the processor 102 to try to find a contiguous region of the memory 104 of the requested size that is currently free. If a region of the memory 104 of the requested size is found, then that region of the memory 104 is allocated and the allocated region of the memory 104 is identified to the process that made the allocation request, for example by the malloc function returning a pointer to (i.e. an indicator of a memory address for) that region of the memory 104. If a region of the memory 104 of the requested size could not be found (for example, if there is not sufficient unused memory to provide a contiguous block of memory of the requested size), then this failure may be indicated to the process, for example by the malloc function returning a NULL pointer.
It will be appreciated that other programming languages may use other functions accordingly (such as the function new in C++).
If memory that has been dynamically allocated is not subsequently deallocated (i.e. freed, or released, for use by another process, or for use by the same process at a later point in time), then a so-called “memory leak” occurs. In this situation, the amount of unallocated memory in the memory 104 may continue to decrease, possibly reaching the stage at which there is no more memory free in the memory 104 for allocation to a process.
Thus, associated with dynamic memory allocation is dynamic memory deallocation. When a process no longer requires a region of the memory 104 that had been dynamically allocated for it, then the process may (and should) deallocate that memory region. For example, in the C programming language, a dynamic memory deallocation may be achieved using the C-library function void free (void* pointer), which has as an input parameter a pointer to the memory region to be deallocated (such as the pointer that was initially returned by the call to the function malloc that initially allocated that region of the memory 104). The processor 102 then records that this memory region is no longer allocated to a process, i.e. it is now free and may be allocated again. As discussed above, this may be achieved in numerous ways by the processor 102 and the operating system being run by the computer system 100.
The processor 102 may spend a large amount of processing time processing a dynamic memory allocation request as it tries to find a region in the memory 104 of the requested size. For example, when the computer system 100 is initialised and begins to execute a first process, the usage of the memory 104 is quite low and so it will be relatively easy to identify a suitable memory region in response to a dynamic memory allocation request. However, once the computer system 100 has been running for some time, and is executing a large number of processes, the usage of the memory 104 may be quite high and so it will be relatively harder to identify a suitable memory region in response to a dynamic memory allocation request. This is compounded by the fact that the memory 104 will become fragmented over time, i.e. portions of allocated memory will be interleaved with portions of free memory, which may therefore make it harder to find a contiguous memory region of a requested size, even though the combined amount of free memory (when considered as non-fragmented memory) may still be more than sufficient for the requested allocation size. This problem is particularly relevant to systems which inherently have a relatively small memory 104 (such as a mobile telephone).
One known approach to tackling this problem is for the processor 102 and the operating system to store and use so-called “free-lists” to handle dynamic memory allocation and deallocation. The use of free-lists is described with reference to FIGS. 2 and 4 of the accompanying drawings, in which FIG. 2 is a flow-diagram schematically illustrating known processing for dynamic memory allocation using free-lists, whilst FIG. 4 is a flow-diagram schematically illustrating known processing for dynamic memory deallocation using free-lists.
Before describing the use of free-lists in detail, a brief overview is appropriate. A free-list is a list (or pool or store) of identifiers, where each identifier identifies a corresponding region of the memory 104 that had been allocated for a process (for example, in response to that process calling the malloc function) but that is currently not required by any of the one or more processes (for example, the process to which the memory region had been allocated has indicated that it no longer needs that memory region by calling the free function). The identifier may be, for example, a memory pointer, i.e. an address within the memory 104.
A free-list has an associated predetermined size value S. For a free-list having an associated size value S, the size of each of the regions of the memory 104 identified by identifiers stored in a free-list is that associated size value S (excluding any headers or footers of the memory regions that may be used for the memory management).
Additionally, a free-list with associated size value S has an associated predetermined threshold τ(S). The threshold τ(S) is the maximum number of identifiers that can be stored in that free-list. The actual number of identifiers currently stored in the free-list that has an associated size value S is represented as the value N(S). Hence, N(S) lies in the range 0≦N(S)≦τ(S). Naturally, in these known systems, the threshold value τ(S) is greater than 0, as otherwise the free-list would not be able to store any identifiers.
Thus, a free-list with associated size value S identifies up to τ(S) regions of the memory 104 of size S, where each of these regions (i) was initially dynamically allocated for a corresponding process and (ii) is no longer required by any process, i.e. these memory regions are available for use. However, a memory region identified by an identifier in a free-list has not actually been deallocated by the processor 102 and the underlying operating system, so that, save for the use of the free-lists (as discussed below) the processor 102 would still consider this memory region to not be available for allocation to a process.
A free-list may be implemented as a first-in-first-out buffer or a last-in-last-out buffer, or any other suitable list structure as is well known in this field of technology.
A predetermined plurality of free-lists are used and maintained, each with different associated size values S. For example, eight free-lists may be maintained to handle dynamic memory allocation and deallocation, with associated size values of 100 bytes, 500 bytes, 1000 bytes, 1500 bytes, 2000 bytes, 5000 bytes, 10000 bytes and 65535 bytes. The corresponding thresholds may be, for example, τ(100)=3, τ(500)=1, τ(1000)=4, τ(1500)=2, τ(2000)=1, τ(5000)=2, τ(10000)=1, τ(65535)=4. Known systems may make use of an alternative predetermined number of free-lists, and these free-lists may have different predetermined associated size values and thresholds.
FIG. 2 is a flow-diagram schematically illustrating known processing 200 for dynamic memory allocation using free-lists.
At a step S202, a dynamic memory allocation request is called by a process, requesting allocation of a region of the memory 104 of a specified size S_req.
At a step S204, the free-list to use for this dynamic memory allocation request is identified. This is achieved by identifying the smallest size value S associated with the free-lists that is at least as large as the size S_req, i.e. the size value S is a size value suitable for the requested memory allocation. For example, with the above configuration of size values and thresholds: (i) if S_req=130 bytes, then the identified size value is S=500; (ii) if S_req=3400 bytes, then the identified size value is S=5000; and (iii) if S_req=1500 bytes, then the identified size value is S=1500. In this way, the smallest size of the memory regions accommodated by the free-lists that is sufficiently large for the requested memory allocation is determined.
At a step S206, it is determined whether the identified free-list with associated size value S is empty, i.e. whether it is currently storing any identifiers. If N(S)>0 (i.e. that free-list is not empty as there is at least one identifier stored in this free-list), then processing continues at a step S208; otherwise, if N(S)=0 (i.e. that free-list is empty as there are no identifiers stored in this free-list), then processing continues at a step S212.
At the step S208 (i.e. when the identified free-list is not empty), one of the identifiers in the identified free-list is chosen. The memory region identified by that identifier is then identified (indicated) to the requesting process, for example by returning a pointer to that memory region in response to the call to the malloc function. In this way, the process has been assigned (provided with) a suitably-sized memory region without the processor 102 having to actually search the memory 104 for a suitably-sized memory region to allocate to the process.
Then, at a step S210, the chosen identifier is removed from the identified free-list and the value of N(S) is decremented by one to update the number of identifiers in that free-list accordingly.
Alternatively, at the step S212 (i.e. when the identified free-list is empty), the processor 102, using the underlying operating system functionality, actually performs an allocation of a memory region of the identified size S. Methods for doing this are discussed above, i.e. a search for a contiguous region of free memory having the identified size S is performed and the memory region that is found is marked as being allocated.
When a region of the memory 104 having the identified size S has been found, then at a step S214 that memory region is identified (indicated) to the process requesting the dynamic memory allocation, for example by returning a pointer to that memory region in response to the call to the malloc function.
If the search at the step S212 had failed to find a contiguous memory region of the identified size S that is free, then this failure would be indicated to the process requesting the dynamic memory allocation, for example, by returning a NULL pointer in response to the call to the malloc function and the process would perform exception handling as appropriate.
FIG. 4 is a flow-diagram schematically illustrating known processing 400 for dynamic memory deallocation using free-lists.
At a step S402, a dynamic memory deallocation request is called by a process, requesting deallocation of a particular region of the memory 104.
At a step S404, the size S of that region of the memory 104 is identified. For example, if the above-described memory management scheme using headers and footers is used, then the size of that memory region can be determined by reading that memory region's header or footer. However, other methods for recording and identifying the size of an allocated region of memory are known when other memory management schemes are used.
The identified size S will correspond to the size value associated with one of the free-lists, as this memory region would have been dynamically allocated using the method 200 described above with reference to FIG. 2 and which always allocates a memory region with a size equal to the size value associated with one of the free-lists. In this way, the free-list to use for this dynamic memory deallocation request is identified.
At a step S406, it is determined whether the identified free-list with associated size value S is full, i.e. whether N(S)=τ(S).
If the identified free-list is full (i.e. the number of identifiers stored in the identified free-list equals the threshold associated with that free-list, N(S)=τ(S)), then processing continues at a step S408 at which that memory region is deallocated. This is achieved by the processor 102 and the underlying operating system, which mark this memory region as now being free for re-allocation.
However, if the number of identifiers stored in the identified free-list is less than the threshold associated with that free-list (i.e. N(S)<τ(S)), so that the free-list is not full, then processing continues at a step S410. At the step 410, instead of deallocating the memory region and marking it free for re-allocation, an identifier of that memory region is added to that free-list. Then at a step S412, the value of N(S) is incremented by one to update the number of identifiers in the free-list accordingly.
Thus, the use of free-lists may avoid the usually large amount of processing that is required to search for a memory region in response to a dynamic memory allocation request. Additionally, the processing required in response to a dynamic memory deallocation request is reduced. Furthermore, the use of free-lists helps reduce external fragmentation of the memory 104, i.e. it helps avoid the situation in which regions of allocated memory are interspersed between regions of free memory in such a way that the size of a contiguous region of free memory is too small to be of use. This is due to the allocated regions of memory being of predetermined fixed sizes (i.e. one of the associated size values), which makes arranging these allocated memory regions in the memory 104 easier.
Whilst using free-lists helps reduce the amount of processing that the processor 102 needs to perform for dynamic memory allocation and deallocation, the fact that the memory regions identified by the free-lists are not actually deallocated means that the amount of memory marked as being free in the memory 104 is not as large as it would have been if free-lists were not being used.
Furthermore, the development of applications for execution on the computer system 100 often involves integrating many software modules that have been developed by different parties. The various modules will, invariably, have been developed and written in different styles, with different amounts of the memory 104 being allocated for various functions. Additionally, some modules will have used a large amount of static memory allocation compared to other modules, and some modules will use a large amount of dynamic memory allocation compared to other modules.
Additionally, when an application has been developed for one computer platform 100, but is to be ported across to a different platform, the methods and styles of memory allocation used for the application may not be suitable for this different platform (due to factors such as different sizes of memory available on different platforms and different processing power between different platforms).
Thus, integrating the various different modules and re-working an application for a different computing platform can occupy a large amount of a development project lifetime, in terms of analysis of memory usage and allocation, development and testing of the various modules and their integration and optimisation. For example, when the size of the memory 104 is quite small (such as a memory 104 for a mobile telephone or a personal digital assistant), it is important to ensure that the memory allocation required by all of the modules that are run concurrently does not exceed the amount of memory that is provided by the memory 104, as otherwise one or more of the applications being executed by the computer system 100 may fail. These checks can be a very involved task.